//
// Created by admin on 2020/7/17.
//

#include "demo.h"

/*
 * 初始化栈，栈指针为空；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
LinkStack InitStack(){
    LinkStack linkStack = NULL;
    return linkStack;
}

/*
 * 当栈指针有值时，不为空；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
int StackEmpty(LinkStack S){
    if (!S){
        return 1;
    } else{
        return 0;
    }
}

/*
 * 遍历栈链，当栈指针为空时，意味着到达栈底，结束循环；
 * 时间复杂度:O(n)
 * 空间复杂度:O(1)
 */
int StackLength(LinkStack S){
    int length = 0;
    while (S){
        S = S->next;
        length++;
    }
    return length;
}

/*
 * 假释放；
 * 将栈指针指向空；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
void ClearStack(LinkStack *S){
    *S = NULL;
}
/*
 * 真释放；
 * 将栈中每个元素都释放，将栈指针指向空；
 * 时间复杂度:O(n)
 * 空间复杂度:O(1)
 */
void ClearStack1(LinkStack *S){
    LinkStack P = *S;
    while (P){
        LinkStack D = P;
        P = P->next;
        free(D);
    }
    *S = NULL;
}
/*
 * 假销毁；
 * 将栈中每个元素都释放，将栈指针指向空；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
void DestroyStack(LinkStack *S){
    *S = NULL;
}

/*
 * 真销毁；
 * 将栈中每个元素都释放，将栈指针指向空；
 * 时间复杂度:O(n)
 * 空间复杂度:O(1)
 */
void DestroyStack1(LinkStack *S){
    LinkStack P = *S;
    while (P){
        LinkStack D = P;
        P = P->next;
        free(D);
    }
    *S = NULL;
}

/*
 * 如果栈顶减栈底小于栈可用容量，则添加；
 * 将数据赋值给栈顶，并将栈顶上移动一位；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
void Push(LinkStack *S,int data){
    LinkStack P = (LinkStack)malloc(sizeof(LinkStack));
    P->data = data;
    P->next = *S;
    *S = P;
}

/*
 * 如栈不为空，则出栈；
 * 将栈顶下移动一位，取出数据并返回；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
int Pop(LinkStack *S){
    if (*S){
        int temp = (*S)->data;
        LinkStack P = *S;
        *S = (*S)->next;
        free(P);
        return temp;
    } else{
        printf("Stack Is Empty!");
    }
}

/*
 * 如栈不为空，则取数据；
 * 将栈顶下移一位，取出数据并返回；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
int GetTop(LinkStack S){
    if (S){
        return (*S).data;
    } else{
        printf("Stack Is Empty!");
    }
}